package leetcode_800;

/**
 *@author 周杨
 *DailyTemperatures_739 给定一个数组 返回一个数组 数组里的每个元素 是比这个元素大的下一个元素的Index
 *describe:用位移数组 能在O(n)时间复杂度内解决问题 AC 94%
 *2018年10月15日 下午1:19:33
 */
public class DailyTemperatures_739 {
	public int[] dailyTemperatures(int[] T) {
        int dp[]=new int[T.length];
        for(int i=T.length-2;i>=0;--i) {
        	if(T[i]<T[i+1]) {
        		dp[i]=1;
        	}
        	else {//开始搜索dp数组
        		int index=1;
        		while(index+i<T.length) {
        			if(dp[index+i]==0)//找不到比其大的了
        				break;
        			else {
        				index+=(dp[index+i]);//往后找下一个大的
        				if(T[i]<T[index+i]) {
        					dp[i]=index;
        					break;
        				}
        			}
        		}
        	}
        }
        return dp;
    }
}
